﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace FindSubarrayWithGivenGum
{
    /// <summary>
    /// Given an unsorted array of nonnegative integers, find a continous subarray which adds to a given number.
    /// </summary>
    public static class ArrayExtension
    {
        /// <summary>
        /// Complexity O(n^2)
        /// </summary>
        /// <param name="input"></param>
        /// <param name="sum"></param>
        /// <returns></returns>
        public static bool GetSubArraysWithSum(this int[] input, int sum)
        {

            for (int i = 0; i < input.Length; i++)
            {
                int current = input[i];

                for (int j = i+1; j < input.Length; j++)
                {
                    if (current == sum)
                    {
                        Console.WriteLine("Sum found between {0} - {1}", i, j);
                        return true;
                    }

                    if (current > sum || j == input.Length)
                        break;

                    current += input[j];
                }
            }

            return false;
        }

        public static bool GetSubArraysWithSumOptimized(this int[] input, int sum)
        {
            int current_sum = 0;

            int begin = 0;
            int end = 0;

            for (int i = 0; i < input.Length; i++)
            {
                current_sum += input[i];

                if (sum == current_sum)
                {
                    end = i;

                    Console.WriteLine("Sum found between index {0} - {1}", begin, end);
                    return true;
                }

                if (current_sum > sum || current_sum < 0)
                {
                    current_sum = 0;
                    i = begin++;
                }              
            }

            return false;
        }        
    }
}
